| Applied Mathematics for Class 11th & 12th (Concepts and Questions) | ||
|---|---|---|
| 11th | Concepts | Questions |
| 12th | Concepts | Questions |
| Content On This Page | ||
|---|---|---|
| Factorial | Fundamental Principle of Counting | Permutations |
| Combinations | ||
Chapter 6 Permutations and Combinations (Concepts)
Welcome to this essential exploration of Permutations and Combinations, the fundamental mathematical tools governing the art and science of counting. In applied mathematics and numerous related fields, the ability to systematically determine the number of ways objects can be arranged or selected is not just a theoretical exercise but a crucial skill. Whether calculating probabilities, analyzing statistical data, designing algorithms in computer science, optimizing logistical plans, or making informed decisions under constraints, the principles discussed here provide the necessary framework. This chapter moves beyond simple enumeration, equipping you with powerful, structured techniques – the Fundamental Principle of Counting, Permutations, and Combinations – to tackle complex counting problems methodically and accurately.
The journey begins with the bedrock concept: the Fundamental Principle of Counting (FPC). This principle branches into two key rules that underpin most combinatorial analysis. The Multiplication Principle states that if one operation can be performed in $m$ ways and, following it, a second independent operation can be performed in $n$ ways, then the two operations can be performed in sequence in $m \times n$ ways. Conversely, the Addition Principle applies when dealing with mutually exclusive options: if one task can be performed in $m$ ways and another task can be performed in $n$ ways, and the two tasks cannot be performed simultaneously, then either one or the other can be performed in $m + n$ ways. To facilitate calculations involving sequential multiplication of decreasing integers, we introduce the indispensable factorial notation, $n!$, defined as the product of the first $n$ natural numbers: $n! = n \times (n-1) \times (n-2) \times \dots \times 3 \times 2 \times 1$, with the special definition $0! = 1$.
Building upon the FPC, we explore Permutations, which deal with arrangements of objects where the order is significant. How many ways can runners finish a race? How many different passwords can be formed? These are permutation problems. The number of permutations of $n$ distinct objects taken $r$ at a time is denoted by $P(n, r)$ or $^nP_r$ and calculated using the formula $P(n, r) = \frac{n!}{(n-r)!}$. We also address scenarios where not all objects are distinct; for example, arranging the letters in the word "MISSISSIPPI". In such cases, the formula adjusts to $\frac{n!}{p_1! p_2! \dots p_k!}$, where $n$ is the total number of objects, and $p_1, p_2, \dots, p_k$ are the frequencies of each distinct object. Arrangements in a circle, known as circular permutations, are also considered, typically calculated as $(n-1)!$ for $n$ distinct objects.
In contrast to permutations, Combinations focus on selections where the order does not matter. How many ways can a committee be chosen from a group? How many different hands of cards can be dealt? These scenarios require combinations. The number of combinations of $n$ distinct objects taken $r$ at a time is denoted by $C(n, r)$, $\binom{n}{r}$, or $^nC_r$, and calculated using the formula $C(n, r) = \frac{n!}{r!(n-r)!}$. This formula finds extensive application in:
- Forming committees, teams, or groups where internal arrangement doesn't matter.
- Selecting items from a larger set (e.g., choosing books, questions on an exam).
- Solving geometric problems, such as determining the number of lines ($\binom{n}{2}$) or triangles ($\binom{n}{3}$) that can be formed from $n$ non-collinear points (adjustments are needed if collinear points exist).
Factorial
In mathematics, especially within the realm of counting and probability, the Factorial of a number is a specific operation that simplifies the representation and calculation of products involving sequences of consecutive integers. It is a fundamental concept used extensively in permutations and combinations.
Definition of Factorial
The Factorial of a non-negative integer $n$, denoted by $n!$ (read as "$n$ factorial"), is defined as the product of all positive integers from 1 up to $n$.
For any positive integer $n \geq 1$, the factorial is calculated as:
$$n! = n \times (n-1) \times (n-2) \times ... \times 3 \times 2 \times 1$$
... (47)
For example:
- $1! = 1$
- $2! = 2 \times 1 = 2$
- $3! = 3 \times 2 \times 1 = 6$
- $4! = 4 \times 3 \times 2 \times 1 = 24$
Special Case: Factorial of Zero
The factorial of zero is defined as 1.
$$0! = 1$$
... (48)
This definition is crucial for maintaining consistency in various mathematical formulas, particularly those involving permutations and combinations (e.g., the formula for $P(n, n)$ or $C(n, 0)$). It can also be justified by considering the recursive definition of factorial or by combinatorial arguments (there is one way to arrange zero objects - do nothing).
Recursive Relation of Factorial
For any integer $n \geq 1$, the factorial $n!$ can be expressed in terms of the factorial of the preceding integer $(n-1)!$.
$$n! = n \times (n-1)! \quad (\text{for } n \geq 1)$$
... (49)
Derivation: From the definition, $n! = n \times (n-1) \times (n-2) \times ... \times 3 \times 2 \times 1$. The part $(n-1) \times (n-2) \times ... \times 3 \times 2 \times 1$ is exactly the definition of $(n-1)!$.
Thus, $n! = n \times (n-1)!$.
This recursive property is particularly useful for simplifying expressions involving factorials and for calculating factorials iteratively. For example:
- $5! = 5 \times 4!$
- $7! = 7 \times 6! = 7 \times 6 \times 5!$
The definition $0! = 1$ is consistent with this recursive relation. If we put $n=1$ in the formula $n! = n \times (n-1)!$, we get $1! = 1 \times (1-1)! \implies 1! = 1 \times 0!$. Since $1! = 1$, this implies $1 = 1 \times 0!$, which means $0! = 1$.
Factorials of Non-Integers and Negative Integers
The factorial function is defined only for non-negative integers. The factorial of a negative integer or a non-integer (like fractions or decimals) is not defined in the standard context of elementary mathematics. The definition is rooted in counting discrete objects.
Applications of Factorial
The factorial function is a cornerstone in many areas of mathematics:
Permutations: The number of ways to arrange a set of $n$ distinct objects in a specific order is given by $n!$. For example, there are $4! = 24$ ways to arrange 4 distinct books on a shelf.
Combinations: The formulas for calculating the number of ways to choose a subset of objects from a larger set (where the order of selection doesn't matter) involve factorials. The number of ways to choose $r$ objects from $n$ distinct objects is given by $C(n, r) = \frac{n!}{r!(n-r)!}$.
Probability: Factorials are extensively used in calculating probabilities, especially in problems involving counting possible outcomes or arrangements of events.
Series Expansions: Factorials appear in the denominators of terms in the Taylor series and Maclaurin series expansions of many important mathematical functions, such as the exponential function ($e^x$) and trigonometric functions ($\sin x$, $\cos x$).
Example 1. Evaluate $\frac{8!}{6!}$.
Answer:
We need to evaluate the expression $\frac{8!}{6!}$.
We can use the recursive property $n! = n \times (n-1)!$ to expand the numerator $8!$ until we reach $6!$.
$$8! = 8 \times (8-1)! = 8 \times 7!$$
Apply the property again to $7!$:
$$8! = 8 \times (7 \times (7-1)!) = 8 \times 7 \times 6!$$
... (i)
Now substitute this expression for $8!$ into the given fraction:
$$\frac{8!}{6!} = \frac{8 \times 7 \times 6!}{6!}$$
[Substitute from (i)]
Since $6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$, which is a non-zero value, we can cancel out the common factor $6!$ from the numerator and the denominator:
$$= 8 \times 7$$
[Cancelling $6!$]
Perform the multiplication:
$$= 56$$
... (ii)
Thus, the value of $\frac{8!}{6!}$ is 56.
Alternate Method (Direct Calculation):
Calculate the exact values of $8!$ and $6!$ and then divide.
$$8! = 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 40320$$
$$6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$$
Perform the division:
$$\frac{8!}{6!} = \frac{40320}{720}$$
$$= \frac{4032}{72}$$
We can perform long division or simplify the fraction:
$$\begin{array}{r} 56\phantom{)} \\ 72{\overline{\smash{\big)}\,4032}} \\ \underline{-360}\phantom{)} \\ 432\phantom{)} \\ \underline{-432}\phantom{)} \\ 0\phantom{)} \end{array}$$$$= 56$$
... (iii)
Both methods yield the same result, 56. The recursive method is generally more efficient when dealing with ratios of factorials.
Example 2. If $\frac{1}{8!} + \frac{1}{9!} = \frac{x}{10!}$, find the value of $x$.
Answer:
We are given the equation $\frac{1}{8!} + \frac{1}{9!} = \frac{x}{10!}$.
We can express the larger factorials in terms of the smallest factorial present, which is $8!$.
Using the recursive property:
$$9! = 9 \times 8!$$
$$10! = 10 \times 9! = 10 \times (9 \times 8!) = 90 \times 8!$$
Substitute these into the given equation:
$$\frac{1}{8!} + \frac{1}{9 \times 8!} = \frac{x}{90 \times 8!}$$
... (i)
Now, find a common denominator for the terms on the left side, which is $9 \times 8!$:
$$\frac{9}{9 \times 8!} + \frac{1}{9 \times 8!} = \frac{x}{90 \times 8!}$$
Combine the terms on the left side:
$$\frac{9 + 1}{9 \times 8!} = \frac{x}{90 \times 8!}$$
$$\frac{10}{9 \times 8!} = \frac{x}{90 \times 8!}$$
... (ii)
Now we have an equation with $x$. To solve for $x$, we can multiply both sides by $90 \times 8!$ (since $90 \times 8! \neq 0$).
$$x = \frac{10}{9 \times 8!} \times (90 \times 8!)$$$$
[Multiply both sides of (ii) by $90 \times 8!$]
Cancel the common factor $8!$ and simplify:
$$x = \frac{10}{9} \times 90$$
[Cancelling $8!$]
$$x = 10 \times \frac{90}{9} = 10 \times 10$$
$$x = 100$$
... (iii)
The value of $x$ is 100.
Fundamental Principle of Counting
In combinatorics and probability, we frequently need to determine the number of ways in which certain events can occur or tasks can be performed. The Fundamental Principle of Counting provides basic rules for this purpose. It is primarily divided into two parts: the Multiplication Principle and the Addition Principle.
The Multiplication Principle (or Fundamental Principle of Multiplication)
The Multiplication Principle is used when a task or event involves a sequence of steps, and the number of ways to perform each step is known. It states that if a procedure can be broken down into a sequence of stages, and there are a fixed number of ways to perform each stage, then the total number of ways to perform the entire procedure is the product of the number of ways to perform each stage.
More formally: If an event or a process can be performed in $m$ different ways, and following this event, another event or process can be performed in $n$ different ways, then the total number of ways in which these two events can occur in the specified order is $m \times n$.
This principle can be extended to any finite number of events. If there are $k$ sequential events or steps, and the first event can occur in $n_1$ ways, the second event can occur in $n_2$ ways (regardless of how the first event occurred), the third event can occur in $n_3$ ways (regardless of how the first two events occurred), and so on, up to the $k$-th event which can occur in $n_k$ ways, then the total number of ways all $k$ events can occur in the defined sequence is the product of the number of ways for each event:
$$\text{Total Ways} = n_1 \times n_2 \times ... \times n_k$$
... (50)
Examples Illustrating the Multiplication Principle:
Example 1. A restaurant offers 3 types of starters and 5 types of main courses. How many different ordered pairs of (starter, main course) can a customer choose?
Answer:
The process of choosing a meal involves two sequential steps:
Step 1: Choose a starter. This event can occur in $m = 3$ different ways (since there are 3 types of starters).
Step 2: Choose a main course. This event can occur in $n = 5$ different ways (since there are 5 types of main courses).
According to the Multiplication Principle, the total number of ways to choose both a starter and a main course is the product of the number of ways for each step.
Total number of different meal combinations $= (\text{Number of starter choices}) \times (\text{Number of main course choices})$
$$= 3 \times 5$$
$$= 15$$
... (i)
A customer can choose from 15 different combinations of a starter and a main course.
Example 2. How many 3-digit numbers can be formed using the digits 1, 2, 3, 4, 5 if repetition of digits is allowed?
Answer:
We need to form a 3-digit number. A 3-digit number has three places: the hundreds place, the tens place, and the units place. Forming the number involves filling these three places sequentially.
The available digits are {1, 2, 3, 4, 5}. There are 5 distinct digits.
Step 1: Fill the hundreds place. We can choose any of the 5 digits. Number of options for the hundreds place = 5.
Step 2: Fill the tens place. Since repetition of digits is allowed, we can again use any of the 5 digits, regardless of what was chosen for the hundreds place. Number of options for the tens place = 5.
Step 3: Fill the units place. Since repetition is allowed, we can again choose any of the 5 digits. Number of options for the units place = 5.
Using the Multiplication Principle (Equation 50), the total number of ways to form the 3-digit number is the product of the number of options for each place:
Total number of 3-digit numbers $= (\text{Options for hundreds}) \times (\text{Options for tens}) \times (\text{Options for units})$
$$= 5 \times 5 \times 5$$
$$= 125$$
... (i)
125 different three-digit numbers can be formed using the digits 1, 2, 3, 4, 5 with repetition allowed.
Example 3. How many 3-digit numbers can be formed using the digits 1, 2, 3, 4, 5 if repetition of digits is NOT allowed?
Answer:
We need to form a 3-digit number using distinct digits from the set {1, 2, 3, 4, 5}. There are 5 distinct digits available.
Step 1: Fill the hundreds place. We can choose any of the 5 digits. Number of options for the hundreds place = 5.
Step 2: Fill the tens place. Since repetition is NOT allowed, the digit used for the hundreds place cannot be used again. So, we have 4 remaining digits to choose from for the tens place. Number of options for the tens place = 4.
Step 3: Fill the units place. We have already used two distinct digits (one for hundreds, one for tens). So, we have 3 remaining digits to choose from for the units place. Number of options for the units place = 3.
Using the Multiplication Principle (Equation 50), the total number of ways to form the 3-digit number is the product of the number of options for each place:
Total number of 3-digit numbers $= (\text{Options for hundreds}) \times (\text{Options for tens}) \times (\text{Options for units})$
$$= 5 \times 4 \times 3$$
$$= 60$$
... (i)
60 different three-digit numbers can be formed using the digits 1, 2, 3, 4, 5 without repetition.
The Addition Principle (or Fundamental Principle of Addition)
The Addition Principle is used when a task can be performed in one of several mutually exclusive ways (meaning, choosing one way excludes choosing the others). It states that if an event can occur in $m$ different ways, and another event can occur in $n$ different ways, and these two events cannot occur simultaneously (they are mutually exclusive), then the total number of ways for either event to occur is $m + n$.
This principle can be extended to any finite number of mutually exclusive events. If event 1 can occur in $n_1$ ways, event 2 can occur in $n_2$ ways, ..., and event $k$ can occur in $n_k$ ways, and no two of these events can occur simultaneously, then the total number of ways that exactly one of these events can occur is the sum of the number of ways for each event:
$$\text{Total Ways} = n_1 + n_2 + ... + n_k$$
... (51)
Examples Illustrating the Addition Principle:
Example 4. A student can choose a project from 3 projects offered in Subject A or 4 projects offered in Subject B. How many choices does the student have if they must choose only one project?
Answer:
The student needs to choose a single project. The choice can either be from Subject A OR from Subject B. These are two mutually exclusive events (the student cannot choose a project that is simultaneously in both Subject A and Subject B, and the choice of one project excludes the choice of another for this specific task).
Event 1: Choosing a project from Subject A. This can occur in 3 ways.
Event 2: Choosing a project from Subject B. This can occur in 4 ways.
Using the Addition Principle (Equation 51), the total number of choices for the student is the sum of the number of ways for each event.
Total number of choices $= (\text{Choices from Subject A}) + (\text{Choices from Subject B})$
$$= 3 + 4$$
$$= 7$$
... (i)
The student has 7 choices for the project.
Combining the Principles
Many problems require the use of both the Multiplication and Addition Principles. Use the Multiplication Principle when a task involves a sequence of steps, and use the Addition Principle when a task can be done in one of several mutually exclusive ways.
Example 5. From a committee of 5 men and 4 women, how many ways can we select a committee of 3 members that has either 2 men and 1 woman OR 1 man and 2 women?
Answer:
The task is to select a committee of 3 members. This task can be done in two mutually exclusive ways (either case 1 OR case 2).
Case 1: Selecting a committee with exactly 2 men and 1 woman.
This involves two steps:
- Step 1a: Select 2 men from 5 men. (We'll learn how to calculate combinations later, but assume there's a number of ways, $W_M$).
- Step 1b: Select 1 woman from 4 women. (Assume there's a number of ways, $W_W$).
By the Multiplication Principle, the number of ways for Case 1 is $W_M \times W_W$.
Case 2: Selecting a committee with exactly 1 man and 2 women.
This also involves two steps:
- Step 2a: Select 1 man from 5 men. ($W'_M$)
- Step 2b: Select 2 women from 4 women. ($W'_W$)
By the Multiplication Principle, the number of ways for Case 2 is $W'_M \times W'_W$.
Since Case 1 and Case 2 are mutually exclusive (a committee cannot simultaneously have 2 men and 1 woman AND 1 man and 2 women), we use the Addition Principle to find the total number of ways for either case to occur.
Total number of ways $= (\text{Ways for Case 1}) + (\text{Ways for Case 2})$
$$= (W_M \times W_W) + (W'_M \times W'_W)$$$$
(Note: Calculating $W_M, W_W, W'_M, W'_W$ requires knowledge of combinations, which is covered in a later section. This example illustrates the structure of applying the principles.)
Permutations
In combinatorics, when we are interested in the number of ways to arrange a set of objects where the order of the objects is important, we are dealing with Permutations. A permutation is essentially an arrangement of objects in a definite order.
Permutations of $n$ Distinct Objects
Let's consider a set of $n$ distinct objects. We want to find the number of ways to arrange these objects.
Number of Permutations of $n$ distinct objects taken all at a time
This problem asks for the number of ways to arrange all $n$ available distinct objects in a sequence or a row.
Derivation using the Multiplication Principle:
Suppose we have $n$ distinct objects, and we have $n$ positions available to place them (like $n$ seats in a row).
Consider filling the positions one by one:
- For the first position, there are $n$ different objects we can choose from. Number of options = $n$.
- After placing one object in the first position, there are $(n-1)$ distinct objects remaining. So, for the second position, there are $(n-1)$ choices. Number of options = $(n-1)$.
- For the third position, there are $(n-2)$ distinct objects remaining. Number of options = $(n-2)$.
- This process continues until the last position.
- For the $n$-th position, there is only 1 distinct object left to choose. Number of options = 1.
According to the Multiplication Principle (Equation 50), the total number of ways to fill all $n$ positions with the $n$ distinct objects is the product of the number of options for each position:
$$\text{Total arrangements} = n \times (n-1) \times (n-2) \times ... \times 2 \times 1$$
This product is exactly the definition of the factorial of $n$.
$$\text{Number of permutations of } n \text{ distinct objects taken all at a time} = n!$$
... (52)
Example 1. In how many different ways can the letters of the word "ROSE" be arranged?
Answer:
The word "ROSE" has 4 letters: R, O, S, E.
All these 4 letters are distinct.
We need to find the number of ways to arrange these 4 distinct letters, taking all 4 at a time. This is a permutation problem of $n$ distinct objects taken all at a time, where $n=4$.
Using the formula for the number of permutations of $n$ objects taken all at a time (Equation 52):
$$\text{Number of arrangements} = n! = 4!$$
Calculate the factorial:
$$4! = 4 \times 3 \times 2 \times 1 = 24$$
... (i)
The letters of the word "ROSE" can be arranged in 24 different ways.
Number of Permutations of $n$ distinct objects taken $r$ at a time
This problem asks for the number of ways to arrange a smaller subset of $r$ objects selected from a larger set of $n$ distinct objects, where the order of arrangement of the $r$ selected objects matters. This is denoted by $P(n, r)$ or $_nP_r$. Here, $r$ is a non-negative integer and $0 \leq r \leq n$.
Derivation using the Multiplication Principle:
Suppose we have $n$ distinct objects and we want to select and arrange $r$ of them in $r$ positions (like $r$ seats in a row, chosen from $n$ possible objects), where $r \leq n$.
Consider filling the $r$ positions sequentially:
- For the first position, there are $n$ different objects we can choose from. Number of options = $n$.
- After selecting and placing one object, there are $(n-1)$ distinct objects remaining. For the second position, there are $(n-1)$ choices. Number of options = $(n-1)$.
- For the third position, there are $(n-2)$ distinct objects remaining. Number of options = $(n-2)$.
- This continues until we have filled the $r$-th position.
- For the $r$-th position, we have already used $(r-1)$ distinct objects. The number of distinct objects remaining is $n - (r-1) = n - r + 1$. Number of options = $(n - r + 1)$.
According to the Multiplication Principle (Equation 50), the total number of ways to fill the $r$ positions with distinct objects selected from $n$ is the product of the number of options for each position:
$$P(n, r) = n \times (n-1) \times (n-2) \times ... \times (n - r + 1)$$
... (a)
This product contains $r$ terms. We can express this product using factorials by multiplying and dividing by $(n-r)!$:
$$P(n, r) = n \times (n-1) \times ... \times (n - r + 1) \times \frac{(n-r) \times (n-r-1) \times ... \times 1}{(n-r) \times (n-r-1) \times ... \times 1}$$$$
$$= \frac{n \times (n-1) \times ... \times (n - r + 1) \times (n-r)!}{(n-r)!}$$$$
The numerator is the product of integers from $n$ down to 1, which is $n!$.
$$P(n, r) = \frac{n!}{(n-r)!}$$
... (53)
This formula is valid for $0 \leq r \leq n$.
Special Cases:
- When $r = n$: $P(n, n) = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n!$, which matches the formula for arranging all $n$ objects.
- When $r = 0$: $P(n, 0) = \frac{n!}{(n-0)!} = \frac{n!}{n!} = 1$. There is only one way to arrange 0 objects from a set of $n$ (the empty arrangement).
Example 2. How many 3-letter words (with or without meaning) can be formed from the letters of the word "NUMBER" without repetition?
Answer:
The word "NUMBER" has 6 letters: N, U, M, B, E, R. All these letters are distinct.
We need to form 3-letter words using these 6 letters, where the order of the letters matters (e.g., NUM is different from NUB). Repetition is not allowed.
This is a permutation problem of selecting and arranging 3 distinct objects from a set of 6 distinct objects.
Here, $n=6$ (total number of distinct letters) and $r=3$ (number of letters to be arranged).
Using the formula $P(n, r) = \frac{n!}{(n-r)!}$ (Equation 53):
$$P(6, 3) = \frac{6!}{(6-3)!} = \frac{6!}{3!}$$
Calculate the factorials or use the expansion:
$$= \frac{6 \times 5 \times 4 \times 3 \times 2 \times 1}{3 \times 2 \times 1} = \frac{720}{6}$$
Alternatively, using the recursive form $P(n, r) = n \times (n-1) \times ... \times (n-r+1)$:
$$P(6, 3) = 6 \times (6-1) \times (6-2) = 6 \times 5 \times 4$$
[3 terms in the product]
Perform the multiplication:
$$= 120$$
... (i)
120 different 3-letter words can be formed from the letters of the word "NUMBER" without repetition.
Permutations of Objects when not all are Distinct
So far, we have considered permutations of distinct objects. What happens if some of the objects are identical? The number of distinct arrangements decreases because swapping identical objects does not create a new arrangement.
The number of distinct permutations of $n$ objects, where $p_1$ objects are of one kind, $p_2$ objects are of a second kind, ..., $p_k$ objects are of a $k$-th kind, and the remaining objects (if any) are distinct, is given by the formula:
$$\text{Number of distinct permutations} = \frac{n!}{p_1! p_2! ... p_k!}$$
... (54)
Here, $n$ is the total number of objects. If all objects belong to one of the $k$ repeating groups, then $n = p_1 + p_2 + ... + p_k$. If there are $p_{k+1}$ distinct objects, then $n = p_1 + p_2 + ... + p_k + p_{k+1}$. The formula still holds if we consider each distinct object as a group of size 1 (e.g., $p_{k+1}! = 1! = 1$).
Example 3. In how many distinct ways can the letters of the word "INDIA" be arranged?
Answer:
The word "INDIA" has a total of 5 letters.
So, the total number of objects is $n=5$.
Let's list the letters and check for repetitions: I, N, D, I, A.
The letter 'I' appears 2 times.
The letters 'N', 'D', and 'A' each appear 1 time.
Here, we have a total of $n=5$ letters, with one letter 'I' repeating $p_1=2$ times. The other letters (N, D, A) can be considered as groups repeating $1$ time ($p_2=1, p_3=1, p_4=1$), where $n = p_1 + p_2 + p_3 + p_4 = 2+1+1+1=5$.
Using the formula for permutations with repeated objects (Equation 54):
$$\text{Number of distinct arrangements} = \frac{n!}{p_1! p_2! p_3! p_4!}$$
Substitute $n=5$, $p_1=2$, $p_2=1$, $p_3=1$, $p_4=1$:
$$= \frac{5!}{2! 1! 1! 1!} = \frac{5!}{2!}$$
[Since $1! = 1$]
Calculate the factorials:
$$= \frac{5 \times 4 \times 3 \times 2 \times 1}{2 \times 1} = \frac{120}{2}$$
Perform the division:
$$= 60$$
... (i)
The letters of the word "INDIA" can be arranged in 60 distinct ways.
Circular Permutations
Circular permutations deal with arrangements of objects in a circle. Unlike linear arrangements, where the starting and ending positions are distinct, in a circular arrangement, there is no designated start or end point relative to the arrangement itself. Rotating a circular arrangement does not change the relative positions of the objects.
Number of distinct circular permutations of $n$ distinct objects: If we arrange $n$ distinct objects in a circle, we can fix the position of one object anywhere in the circle. The remaining $(n-1)$ objects can then be arranged in the remaining $(n-1)$ positions in $(n-1)!$ ways relative to the fixed object. This accounts for the distinct arrangements.
$$\text{Number of distinct circular permutations} = (n-1)!$$
... (55)
This formula applies when the arrangements are distinguishable when viewed from one side (e.g., people seated around a table, distinguishable when looking down).
Number of distinct circular permutations when clockwise and anticlockwise arrangements are considered the same: If rotating a circular arrangement clockwise or anti-clockwise results in the same arrangement (e.g., arranging beads on a necklace, flowers in a garland), then each distinct linear arrangement corresponds to two arrangements in the circle (one clockwise, one anti-clockwise). However, the formula $(n-1)!$ counts these two as distinct. So, we divide by 2.
$$\text{Number of distinct circular permutations (symmetric)} = \frac{(n-1)!}{2}$$
... (56)
This formula is used when the arrangement can be flipped over or viewed from both sides, making the clockwise and anti-clockwise orders indistinguishable.
Example 4. In how many ways can 5 distinct persons be seated around a circular table?
Answer:
We have 5 distinct persons to be seated around a circular table. The positions are distinct in the sense of relative order (who is to the left/right of whom). We use the formula for circular permutations of $n$ distinct objects.
Here, $n=5$ (number of distinct persons).
Using the formula $(n-1)!$ (Equation 55):
$$\text{Number of ways} = (5-1)! = 4!$$
Calculate the factorial:
$$4! = 4 \times 3 \times 2 \times 1 = 24$$
... (i)
5 distinct persons can be seated around a circular table in 24 ways.
Combinations
In contrast to permutations, where the order of arrangement is important, Combinations deal with the selection of objects from a set where the order of selection does not matter. A combination is essentially a subset of items chosen from a larger collection.
Number of Combinations of $n$ Distinct Objects taken $r$ at a time
This problem asks for the number of ways to select a group of $r$ objects from a set of $n$ distinct objects, without regard to the order in which the $r$ objects are chosen. The number of such combinations is denoted by $C(n, r)$, $_nC_r$, or most commonly, $\binom{n}{r}$ (read as "$n$ choose $r$"). Here, $r$ is a non-negative integer and $0 \leq r \leq n$.
Derivation of the Formula for $C(n, r)$ using Permutations:
We can establish a relationship between permutations and combinations. Consider the task of finding the number of permutations of $n$ distinct objects taken $r$ at a time, $P(n, r)$. This task can be thought of as a two-step process:
1. First, select a group of $r$ objects from the $n$ distinct objects. Let the number of ways to perform this selection (combination) be $C(n, r)$.
2. Second, arrange the $r$ selected objects. Since these $r$ objects are distinct (as they were selected from a set of distinct objects), the number of ways to arrange these $r$ distinct objects among themselves is $r!$ (from Equation 52, permutations of $r$ distinct objects taken all at a time).
According to the Multiplication Principle (Equation 50), the total number of permutations $P(n, r)$ is the product of the number of ways to perform the selection step and the number of ways to perform the arrangement step:
$$P(n, r) = (\text{Number of ways to select } r \text{ objects}) \times (\text{Number of ways to arrange } r \text{ objects})$$
$$P(n, r) = C(n, r) \times r!$$
... (a)
We already know the formula for the number of permutations of $n$ distinct objects taken $r$ at a time: $P(n, r) = \frac{n!}{(n-r)!}$ (Equation 53).
Substitute this expression for $P(n, r)$ into equation (a):
$$\frac{n!}{(n-r)!} = C(n, r) \times r!$$
[Substitute $P(n,r)$ formula into (a)]
Now, we can solve for $C(n, r)$ by dividing both sides of the equation by $r!$ (assuming $r! \neq 0$, which is true for non-negative integers $r$):
$$C(n, r) = \frac{n!}{r! (n-r)!}$$
... (57)
This formula is valid for any integers $n$ and $r$ such that $0 \leq r \leq n$.
Let's check some specific cases:
- When $r = 0$: $C(n, 0) = \frac{n!}{0! (n-0)!} = \frac{n!}{1 \times n!} = 1$. This makes sense; there is only one way to choose 0 objects from a set of $n$ (the empty selection).
- When $r = n$: $C(n, n) = \frac{n!}{n! (n-n)!} = \frac{n!}{n! 0!} = \frac{n!}{n! \times 1} = 1$. This also makes sense; there is only one way to choose all $n$ objects from a set of $n$.
- When $r = 1$: $C(n, 1) = \frac{n!}{1! (n-1)!} = \frac{n!}{1 \times (n-1)!} = \frac{n \times (n-1)!}{(n-1)!} = n$. There are $n$ ways to choose 1 object from a set of $n$.
Example 1. In how many ways can a committee of 3 members be selected from a group of 8 people?
Answer:
We are asked to select a group of 3 members from a larger group of 8 people. The composition of the committee is what matters, not the order in which the members are chosen (e.g., selecting Person A, then B, then C results in the same committee as selecting Person B, then C, then A). This is a combination problem.
Here, $n=8$ (total number of distinct people) and $r=3$ (number of members to be selected for the committee).
Using the formula for the number of combinations of $n$ distinct objects taken $r$ at a time: $C(n, r) = \frac{n!}{r! (n-r)!}$ (Equation 57).
Substitute $n=8$ and $r=3$:
$$C(8, 3) = \frac{8!}{3! (8-3)!} = \frac{8!}{3! 5!}$$
Expand the factorials and simplify. Expand the largest factorial in the numerator until you reach the largest factorial in the denominator ($5!$) to facilitate cancellation.
$$= \frac{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1) \times (5 \times 4 \times 3 \times 2 \times 1)}$$$$
$$= \frac{8 \times 7 \times 6 \times 5!}{3! \times 5!}$$$$
Cancel out $5!$ from the numerator and the denominator (since $5! \neq 0$):
$$= \frac{8 \times 7 \times 6}{3 \times 2 \times 1}$$$$
Simplify the denominator: $3 \times 2 \times 1 = 6$.
$$= \frac{8 \times 7 \times 6}{6}$$$$
Cancel out the 6:
$$= 8 \times 7$$
Perform the final multiplication:
$$= 56$$
... (i)
A committee of 3 members can be selected from a group of 8 people in 56 ways.
Properties of Combinations
Several important properties simplify calculations and provide insights into the nature of combinations:
Symmetry Property: The number of ways to choose $r$ objects from $n$ is equal to the number of ways to choose $(n-r)$ objects from $n$.
$$C(n, r) = C(n, n-r)$$
... (58)
Derivation:
Using the formula for $C(n, r)$ (Equation 57), let's evaluate $C(n, n-r)$:
$$C(n, n-r) = \frac{n!}{(n-r)! (n - (n-r))!}$$$$
[Using formula (57) with $r$ replaced by $n-r$]
Simplify the term in the second bracket in the denominator:
$$= \frac{n!}{(n-r)! (n - n + r)!} = \frac{n!}{(n-r)! r!}$$
... (a)
Compare the result in (a) with the formula for $C(n, r) = \frac{n!}{r! (n-r)!}$. The terms in the denominator are the same, just in a different order (and order of multiplication doesn't matter).
$$= C(n, r)$$
[By definition of $C(n,r)$]
Thus, $C(n, r) = C(n, n-r)$.
This property is very useful for simplifying calculations. For example, $C(10, 8)$ can be calculated as $C(10, 10-8) = C(10, 2) = \frac{10 \times 9}{2 \times 1} = \frac{90}{2} = 45$. Calculating $C(10, 8)$ directly would involve $\frac{10!}{8!2!} = \frac{10 \times 9}{2 \times 1} = 45$, which is more work without the property.
Based on the formula (Equation 57) and the definition of 0! = 1:
$$C(n, 0) = 1$$
(One way to choose zero items)
$$C(n, n) = 1$$
(One way to choose all $n$ items)
$$C(n, 1) = n$$
(n ways to choose one item)
Pascal's Identity: This identity relates combinations with different values of $n$ and $r$.
$$C(n, r) + C(n, r-1) = C(n+1, r)$$
... (59)
This identity forms the basis of Pascal's Triangle, where each entry is the sum of the two entries directly above it. It has combinatorial proofs and algebraic proofs.
Distinction between Permutations and Combinations
It is crucial to differentiate between problems that require permutations and those that require combinations. The key factor is whether the order of selection or arrangement matters.
- Permutation: Used when the order of the selected items is important. It's about arranging objects. Look for keywords like "arrange", "order", "sequence", "distinct ways" (especially when identical items are involved). The result is an ordered arrangement. The formula is $P(n, r) = \frac{n!}{(n-r)!}$ for distinct items, or $\frac{n!}{p_1!p_2!...}$ for items with repetitions.
- Combination: Used when the order of the selected items does not matter. It's about choosing a group or a subset of objects. Look for keywords like "select", "choose", "committee", "group", "subset". The result is an unordered collection. The formula is $C(n, r) = \frac{n!}{r! (n-r)!}$ for distinct items.
Example 2. There are 10 players in a basketball team. In how many ways can a team of 5 players be selected for a match?
Answer:
We need to form a team of 5 players from a group of 10 players. The order in which the players are selected does not affect the composition of the team (a team with players A, B, C, D, E is the same team regardless of the order they were picked). This is a combination problem.
Here, $n=10$ (total number of distinct players) and $r=5$ (number of players to be selected for the team).
Using the formula for the number of combinations of $n$ distinct objects taken $r$ at a time: $C(n, r) = \frac{n!}{r! (n-r)!}$ (Equation 57).
Substitute $n=10$ and $r=5$:
$$C(10, 5) = \frac{10!}{5! (10-5)!} = \frac{10!}{5! 5!}$$
Expand the factorials and simplify. Expand $10!$ until $5!$ to cancel it:
$$= \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5!}{5 \times 4 \times 3 \times 2 \times 1 \times 5!}$$
Cancel out $5!$ and expand $5!$ in the denominator: $5 \times 4 \times 3 \times 2 \times 1 = 120$.
$$= \frac{10 \times 9 \times 8 \times 7 \times 6}{120}$$
Perform the multiplication in the numerator: $10 \times 9 \times 8 \times 7 \times 6 = 90 \times 336 = 30240$.
$$= \frac{30240}{120}$$
Perform the division:
$$= 252$$
... (i)
The calculation with cancellations is often faster:
$$C(10, 5) = \frac{\cancel{10}^{2} \times \cancel{9}^{3} \times \cancel{8}^{1} \times 7 \times \cancel{6}^{1}}{\cancel{5}_1 \times \cancel{4}_1 \times \cancel{3}_1 \times \cancel{2}_1 \times 1} = 2 \times 3 \times 1 \times 7 \times 1$$
$$= 2 \times 3 \times 7 \times \frac{6}{6} = 6 \times 7 \times 1 = 42$$
Let's perform the cancellation carefully:
$$C(10, 5) = \frac{10 \times 9 \times 8 \times 7 \times 6}{5 \times 4 \times 3 \times 2 \times 1}$$$$
Denominator $5 \times 4 \times 3 \times 2 \times 1 = 120$. Numerator $10 \times 9 \times 8 \times 7 \times 6 = 30240$.
Let's cancel terms:
$$\frac{\cancel{10}^{2} \times \cancel{9}^{3} \times \cancel{8}^{1} \times 7 \times \cancel{6}^{1}}{\cancel{5}_{1} \times \cancel{4}_{1} \times \cancel{3}_{1} \times \cancel{2}_{1} \times 1}$$$$
Cancel 10 with 5x2: $\frac{\cancel{10}^{1}}{5 \times 2}$ leaves 1.
Cancel 9 with 3: $\frac{\cancel{9}^{3}}{\cancel{3}_1}$ leaves 3.
Cancel 8 with 4: $\frac{\cancel{8}^{2}}{\cancel{4}_1}$ leaves 2.
Cancel 6 with nothing yet.
So the numerator is $1 \times 3 \times 2 \times 7 \times 6$. Denominator is $1 \times 1 \times 1 \times 1 \times 1 = 1$.
$$= 1 \times 3 \times 2 \times 7 \times 6 = 6 \times 42 = 252$$
The number of ways to select a team of 5 players from 10 is 252.
Combinations of Objects with Repetition
Sometimes, we need to select items from different categories, and we are allowed to select more than one item from the same category. This is combination with repetition. The formula for the number of combinations of $n$ distinct objects taken $r$ at a time with repetition allowed is:
$$\text{Number of combinations with repetition} = C(n+r-1, r) = \binom{n+r-1}{r}$$
... (60)
Where $n$ is the number of distinct types of objects (categories) from which we are selecting, and $r$ is the total number of objects being selected. The order of selection does not matter, and repetition of types is allowed.
Derivation (Brief Idea): This formula can be derived using a method called "stars and bars". Imagine you are distributing $r$ identical items (stars) into $n$ distinct bins (categories). You need $n-1$ "bars" to separate the $n$ bins. The total number of positions for stars and bars is $r + (n-1)$. The number of ways to arrange these $r$ stars and $n-1$ bars is the number of ways to choose the positions for the $r$ stars (or $n-1$ bars) out of the total $n+r-1$ positions, which is $C(n+r-1, r)$.
Example 3. A bakery sells 4 types of cookies: Chocolate, Vanilla, Strawberry, and Butter. In how many ways can a customer choose a dozen (12) cookies?
Answer:
Here, the distinct types of cookies are the categories we can choose from. There are 4 types, so $n = 4$.
The customer wants to choose a total of 12 cookies. This is the number of items being selected, so $r = 12$.
The customer can choose multiple cookies of the same type (repetition is allowed), and the order in which they pick the cookies doesn't matter (getting 3 chocolate and 9 vanilla is one outcome, regardless of the order). This is a combination with repetition problem.
Using the formula for combinations with repetition $C(n+r-1, r)$ (Equation 60):
$$\text{Number of ways} = C(n+r-1, r) = C(4+12-1, 12)$$$$
$$= C(15, 12)$$
Using the symmetry property $C(n, r) = C(n, n-r)$, it's easier to calculate $C(15, 12)$ as $C(15, 15-12) = C(15, 3)$.
$$C(15, 3) = \frac{15!}{3! (15-3)!} = \frac{15!}{3! 12!}$$
[Using formula (57)]
Expand the numerator until $12!$:
$$= \frac{15 \times 14 \times 13 \times 12!}{3 \times 2 \times 1 \times 12!}$$
Cancel out $12!$ and simplify the denominator $3 \times 2 \times 1 = 6$:
$$= \frac{15 \times 14 \times 13}{6}$$$$
Perform cancellations:
$$= \frac{\cancel{15}^{5} \times \cancel{14}^{7} \times 13}{\cancel{6}_{1}} = 5 \times 7 \times 13$$
[Cancel 15 with 3 and 14 with 2]
Perform the final multiplication:
$$= 35 \times 13$$
$$= 455$$
... (i)
The customer can choose a dozen (12) cookies in 455 different ways, with repetition allowed.